package com.hyb.algorithm.data.struct.list;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @Author: huyanbing
 * @Date: 2021/9/18 1:59 下午
 * <p>
 * https://leetcode-cn.com/problems/lru-cache/
 * 146. LRU 缓存机制
 */
public class LRUCache {

    public static void main(String[] args) {
//        ["LRUCache","put","put","get","put","get","put","get","get","get"]
//[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]


        //示例1  --begin
//        LRUCache lruCache = new LRUCache(2);
//
//        lruCache.put(1, 1);
//        lruCache.put(2, 2);
//
//        int ret = lruCache.get(1);
//        System.out.println(ret);
//        lruCache.put(3, 3);
//
//        ret = lruCache.get(2);
//        System.out.println(ret);
//
//        lruCache.put(4, 4);
//
//        ret = lruCache.get(1);
//        System.out.println(ret);
//
//        ret = lruCache.get(3);
//        System.out.println(ret);
//
//        ret = lruCache.get(4);
//        System.out.println(ret);

        //示例1  --end


        //示例2  --begin

        //   ["LRUCache","put","put","put","put","get","get"]
//[[2],[2,1],[1,1],[2,3],[4,1],[1],[2]]
        LRUCache lruCache = new LRUCache(2);

        lruCache.put(2, 1);
        lruCache.put(1, 1);
        lruCache.put(2, 3);
        lruCache.put(4, 1);

        int ret = lruCache.get(1);
        System.out.println(ret);


        ret = lruCache.get(2);
        System.out.println(ret);

        //[null,null,null,null,null,-1,3]

        //示例2  --end
    }


    class Node {
        int val;
        int key;
        Node next;
        Node prev;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

    }

    private List<Integer> list;
    Map<Integer, Node> map;
    int capacity;
    int size = 1;

    Node head;
    Node end;

    public LRUCache(int capacity) {
        list = new LinkedList<>();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        //判断map 中是否有
        //找到该数据位置 并将该元素移动到连表的第一个元素
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);

        map.put(key, node);
        setHead(node);

        return node.val;
    }

    public void put(int key, int val) {

        if (!map.containsKey(key)) {
            Node node = new Node(key, val);
            //添加到队尾
            map.put(key, node);
            if (size > capacity) {
                map.remove(end.key);
                remove(end);
            }
            setHead(node);
            size++;
            return;
        }

        //包含也删除
        Node node = map.get(key);
        remove(node);

        //重新生成一个节点 放入head
        node = new Node(key, val);
        map.put(key, node);
        setHead(node);

    }

    private void setTail(Node node) {
        node.prev = end;
        if (end != null) {
            end.next = node;
        }
        end = node;
        end.next = null;
    }

    private void setHead(Node node) {

        if (head == null) {
            head = node;
            head.prev = null;
            end = node;
            end.next = null;
            return;
        }


        node.next = head;
        head.prev = node;

        if (node.next == null) {
            end = node;
        }

        head = node;

        Node temp = end;

        head.prev = null;

    }

    //删除节点  前后指针处理
    private Node remove(Node node) {

        Node prev = node.prev;
        if (prev != null) {
            prev.next = node.next;
        } else {
            head = node.next;
            if (head != null) {
                head.prev = null;
            }
        }

        Node next = node.next;
        if (next != null) {
            node.next.prev = prev;
        } else {
            end = node.prev;
            if (end != null) {
                end.next = null;
            }
        }

        node.prev = null;
        node.next = null;
        return node;
    }

}
